With increased use of multithreaded applications and multicore processors, data collisions between concurrent threads have become an increasingly significant problem for program developers and testers. Generally, when two threads are constructed to share memory or data in a systematic way (e.g., using thread locks or the like), data collisions do not occur. However, when two threads freely access shared memory, for example a shared object or variable, either might alter the shared object or variable without visibility to the other thread, and the other thread may obtain unexpectedly altered or inconsistent data from the shared object or variable, which is a data collision. Moreover, the occurrence of such a collision may not be immediately apparent to the program. In general, data collisions may cause in-deterministic program behavior.
To explain further, a data collision may be thought of as analogous to a traffic intersection without a traffic light, where the intersection is some shared memory (e.g., a shared register, object, variable, memory barrier, etc) and cars passing through the intersection are as threads freely accessing and updating the shared memory. Eventually two cars may collide at the intersection, just as one thread may update the shared memory during a time when another thread is accessing the shared memory.
Because such data collisions often manifest only later when the corrupt shared memory is inconsistent with program state expected by the program, data collisions have been difficult to detect. Approaches have tended to use complex analysis to predict when a data collision could occur. However, these approaches are often unreliable and may lead to false positive detection, that is, “detection” of a data collision when one has not occurred or when a data collision (an actual corruption of data) cannot occur due perhaps to some mutually exclusive program semantics. In addition, data collision detection has not been able to be performed at the kernel level.
Techniques related to data collision detection are discussed below.